class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if(target == "0000"){
            return 0;
        }
        unordered_set<string> hash(deadends.begin(),deadends.end());
        
        if(hash.count("0000")){
            return -1;
        }
        
        auto changeF = [&](char x){
            return x == '9' ? '0' : x + 1;
        };
        auto changeB = [&](char x){
            return x == '0' ? '9' : x - 1;
        };
        
        auto get = [&](string& s){
            vector<string> path;
            for(int i = 0;i < 4;i++){
                string ss = s;
                ss[i] = changeF(ss[i]);
                path.emplace_back(ss);
                
                ss = s;
                ss[i] = changeB(ss[i]);
                path.emplace_back(ss);
            }
            return path;
        };
      
        vector<string> path;
        
        queue<pair<string,int> > pri_que;
        unordered_set<string> visited = {"0000"};
        
        pri_que.push({"0000",0});
        
        while(!pri_que.empty()){
            auto [k,v] = pri_que.front();
            pri_que.pop();
            
            path = get(k);
            for(string& s : path){
                if(!hash.count(s) && !visited.count(s)){
                    if(s == target){
                        return v+1;
                    }
                    pri_que.emplace(s,v+1);
                    visited.insert(move(s));
                }
            }
        }

       return -1;
    }
};
